#include <cstddef>
#include <limits>
#include <vector>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode()
      : val(0), left(nullptr), right(nullptr){} * TreeNode(int x)
      : val(x),
        left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

void dfs(TreeNode *root, vector<int> &res) {
  if (root == nullptr) {
    return;
  }
  if (root->left != nullptr) {
    dfs(root->left, res);
  }
  res.push_back(root->val);
  if (root->right != nullptr) {
    dfs(root->right, res);
  }
}

bool isValidBST(TreeNode *root) {
  vector<int> res;
  dfs(root, res);
  for (int i = 1; i < res.size(); i++) {
    if (res[i - 1] >= res[i]) {
      return false;
    }
  }
  return true;
}

// 优化内存 只需要记忆前一个访问节点
void dfs_mem(TreeNode *root, int &t, bool &isOver) {
  if (isOver) {
    return;
  }
  if (root->left != nullptr) {
    dfs_mem(root->left, t, isOver);
  }
  if (root->val >= t) {
    isOver = true;
    return;
  }
  t = root->val;
  if (root->right != nullptr) {
    dfs_mem(root->right, t, isOver);
  }
}

bool isValidBST_mem(TreeNode *root) {
  if (root == nullptr) {
    return true;
  }
  int t = numeric_limits<int>::min();
  bool isOver = false;
  dfs_mem(root, t, isOver);

  return !isOver == true;
}